\section{Test Plan}

Our test strategy consisted of writing short to medium length DiGr
programs which would typically print information to the screen, and
creating by hand a "gold standard" of what the output should be
according to the language designers. Additionally, for some test
programs we examined the output in the target language by hand to
check our code.

To run the test suite, we compile and execute every test program and
compare its output to the gold standard. Sometimes, programs would
fail at the front-end level (implying the parser or static semantic
checking was improperly implemented. Sometimes, programs would fail at
the back-end level (output programs in the target language would fail
to compile, or throw a run-time exception, or output something
different from the gold standard). The stage at which the error
occurred allowed us to narrow down bugs along the DiGr compilation
pipeline.

Some tests focused on testing atomic features of the language, from
basic concepts like fundamental types, arithmetic, opt calls, and so
forth, to high-level concepts like graphs, attributes, creation
contexts, etc. Other tests were designed to be complicated and
integrate a wide cross-section of language features.

The test suite was run after every significant change to the parser,
translator, or compiler, to ensure that development had not broken any
previous work. A few tests were written to ensure that necessary
errors at compile time and run time were in fact caught.

Although all team members contributed test programs and ideas for test
programs, and used the test battery to track and fix bugs, Ari was the
member responsible for the upkeep of the suite. The complete list of
test programs (in alphabetical order in our directory) and what
functionality they are designed to test:

\begin{itemize}
\item {\tt anonedge} : proper creation of anonymous edges without runtime errors
\item {\tt arrays } : creating, accessing and modifying  arrays
\item {\tt attributes } : proper creation and access of node and edge
  attributes, both implicitly and explicitly
\item {\tt basiccontext} : proper parsing of complicated tree definition in a connection context
\item {\tt basiccrawl } : a crawl test that integrates many DiGr features
\item {\tt binops} : testing binary operators	
\item {\tt blockorder } : proper handling of control flow (if, if/else, while)
\item {\tt comments} : very simple comment parsing test
\item {\tt contexts } : in-depth test of proper connection context compilation and edge assignment between nodes
\item {\tt crawlargs } : proper indexing and C++ typing of in and out
  variables in function signatures
\item {\tt depthfirsts } : high-concept test of a breadth-first (the name of the test is misleading) and an iterative depth-first search
\item {\tt edgetest } : proper manipulation nodes by traversing edges
\item {\tt factorial} : test of a simple recursive function with in/out variables
\item {\tt fast} : test of fencepost while loop iteration
\item {\tt func } : more complicated test of proper scoping for in/out variables
\item {\tt globals } : testing the 'call' function, changing rules inside crawls, and proper compilation with respect to global namespaces in general
\item {\tt indexattr } : accessing attributes of elements of an array via indexing into the array
\item {\tt nodetest } : creating nodes and edges, plus basic node functionality
\item {\tt opttest} : simple opt-calling test to check proper in/out variable binding
\item {\tt recursivecrawl } : high-concept test with two depth first searches and, specifically, the ability to call a crawl within a crawl
\item {\tt ruleaddby } : proper use of advanced 'addby' feature in a rule
\item {\tt runtime} : check to see that a run-time exception catches illegal indexing
\item {\tt scope } : proper scoping of similarly named variables inside different local scopes
\end{itemize}

\subsection{basiccrawl test}

Here is an example which integrates edges, nodes, crawls and
rules. The DiGr source code is

{\small
\begin{Verbatim}
rule addMarkedChildren {
  int n = 0!
  while (n < current.outedges) {
     edge tmp_edge = current.outedge(n)!
     if (tmp_edge.mark == 1) { 
       node destination = tmp_edge.innode!
       add(destination)!
     } 
     n = n + 1!
  }

}

crawl printId() {
  print (current.id)!
  call!
}


opt main() {

  node n1!
  node n2!
  node n3!
  node n4!
  n1.id = 1!
  n2.id = 2!
  n3.id = 3!
  n4.id = 4!
  n1 -> n2!
  n2 -> n3!
  n2 -> n4!
  edge tmp_edge = n1.outedge(0)!
  tmp_edge.mark = 1! 
  tmp_edge = n2.outedge(1)!
  tmp_edge.mark = 1!

  printId() from n1 with addMarkedChildren!

}
\end{Verbatim}
}


This is a simple program which creates a tree by connecting nodes,
marks some edges with an attribute, and then runs a crawl which prints
the {\tt id} attribute of the current node, while only following edges
which are marked. The output in the target language is (there is
normally a symbol table dump and static semantic checking information
output in the header of the program. In this example, we leave it in):

{\small
\begin{Verbatim}
/*begin formal AST verification
==================
global signature dump: 
main: 
==================
Starting
unimplemented expression
n assigned value
n1 assigned value
n2 assigned value
n3 assigned value
n4 assigned value
tmp_edge assigned value
tmp_edge assigned value
tmp_edge assigned value
==================
symbol table dump: 
--> n1: node
--> n2: node
--> n3: node
--> n4: node
--> tmp_edge: edg
==================
symbol table dump: 
--> current: node
==================
symbol table dump: 
--> current: node
--> n: int
no error!
begin translation to CAST
passed static semantic checking, begin code generation
====================== */

#include ``digr.h''
#include <iostream>
/* actual definition of C++ functions */
void addMarkedChildren(DiGrNode *current, deque<DiGrNode*> *returnQueue) {
int n =  0 ;
while(n < current->OutEdges())
{DiGrEdge *tmp_edge = current->getOutEdge(n);
if(tmp_edge->getAttribute(``mark'') ==  1 )
{DiGrNode *destination = tmp_edge->inNode();
returnQueue->push_back(destination);
}
else{}
n=n +  1 ;
}
}

void printId(DiGrNode *current, void (*rule)(DiGrNode*, deque<DiGrNode*>*)) {
deque<DiGrNode*> *queue = new deque<DiGrNode*>();
queue->push_back(current);
do {
current=queue->front();
queue->pop_front();
std::cout << current->getAttribute(``id'') << std::endl;
rule(current, queue);
} while (queue->size() >  0 );

}

int main() {
try{
DiGrNode *n1 = new DiGrNode();
DiGrNode *n2 = new DiGrNode();
DiGrNode *n3 = new DiGrNode();
DiGrNode *n4 = new DiGrNode();
n1->setAttribute(``id'',  1 );
n2->setAttribute(``id'',  2 );
n3->setAttribute(``id'',  3 );
n4->setAttribute(``id'',  4 );
new DiGrEdge(n1, n2);
new DiGrEdge(n2, n3);
new DiGrEdge(n2, n4);
DiGrEdge *tmp_edge = n1->getOutEdge( 0 );
tmp_edge->setAttribute(``mark'',  1 );
tmp_edge=n2->getOutEdge( 1 );
tmp_edge->setAttribute(``mark'',  1 );
printId(n1, addMarkedChildren);
}
catch(const char *e) {
std::cout << e << std::endl;
}

}
\end{Verbatim}
}

The simple DiGr crawls and rules and implicit queues and references to
nodes are turned into explicit and careful function signatures and a
system of pointers in the target language. When executed, this should
outputs the first node (with an id of 1), follow the marked edge to
node 2, and the follow the marked edge to node 4. Sure enough, the
output is

\begin{Verbatim}
1
2
4
\end{Verbatim}

\subsection{recursivecrawl test}

Another sophisticated example is a test that implements post-order and
in-order depth-first traversals of a tree. It accomplishes this by
leaving the queue empty (in fact, even assigning a blank rule), and
simply recursively calling itself on its children before printing. The
DiGr source code is:

{\small
\begin{Verbatim}
rule blankRule {

}

crawl recurse_to_children_and_print() {

      int n = 0!
      while (n < current.outedges) {
        edge tmp_edge = current.outedge(n)!
        node tmp_node = tmp_edge.innode!
        recurse_to_children_and_print() from tmp_node with blankRule!
        n = n + 1!
     }

     print(current.name)!
}

crawl recurse_inorder() {

      int n = 0!
      while (n < current.outedges) {
        edge tmp_edge = current.outedge(n)!
        node tmp_node = tmp_edge.innode!
        if (tmp_node.name < current.name) {
            recurse_inorder() from tmp_node with blankRule!
        }
        n = n + 1!
     }

     print(current.name)!

     n = 0!
      while (n < current.outedges) {
        edge tmp_edge = current.outedge(n)!
        node tmp_node = tmp_edge.innode!
        if (tmp_node.name > current.name) {
            recurse_inorder() from tmp_node with blankRule!
        }
        n = n + 1!
     }

}

opt main() {

   node binTree[8] = |4 -> (2 -> 1,3), (6 -> 5,7)|!

   node tmp_node = binTree[1]!
   tmp_node.name = 1!
   tmp_node = binTree[2]!
   tmp_node.name = 2!
   tmp_node = binTree[3]!
   tmp_node.name = 3!
   tmp_node = binTree[4]!
   tmp_node.name = 4! 
   tmp_node = binTree[5]!
   tmp_node.name = 5!
   tmp_node = binTree[6]!
   tmp_node.name = 6!
   tmp_node = binTree[7]!
   tmp_node.name = 7!

   node start = binTree[4]!

   print (``post-order!'')!
   recurse_to_children_and_print() from start with blankRule!

   print (``in-order!'')!
   recurse_inorder() from start with blankRule!

}
\end{Verbatim}
}

This compiles to (leaving out the verbose static semantic output and
the symbol table dump) :

{\small
\begin{Verbatim}
#include ``digr.h''
#include <iostream>
/* actual definition of C++ functions */
void blankRule(DiGrNode *current, deque<DiGrNode*> *returnQueue) {

}

void recurse_to_children_and_print(DiGrNode *current, void (*rule)(DiGrNode*, deque<DiGrNode*>*)) {
deque<DiGrNode*> *queue = new deque<DiGrNode*>();
queue->push_back(current);
do {
current=queue->front();
queue->pop_front();
int n =  0 ;
while(n < current->OutEdges())
{DiGrEdge *tmp_edge = current->getOutEdge(n);
DiGrNode *tmp_node = tmp_edge->inNode();
recurse_to_children_and_print(tmp_node, blankRule);
n=n +  1 ;
}std::cout << current->getAttribute(``name'') << std::endl;
} while (queue->size() >  0 );

}

void recurse_inorder(DiGrNode *current, void (*rule)(DiGrNode*, deque<DiGrNode*>*)) {
deque<DiGrNode*> *queue = new deque<DiGrNode*>();
queue->push_back(current);
do {
current=queue->front();
queue->pop_front();
int n =  0 ;
while(n < current->OutEdges())
{DiGrEdge *tmp_edge = current->getOutEdge(n);
DiGrNode *tmp_node = tmp_edge->inNode();
if(tmp_node->getAttribute(``name'') < current->getAttribute(``name''))
{recurse_inorder(tmp_node, blankRule);
}
else{}
n=n +  1 ;
}std::cout << current->getAttribute(``name'') << std::endl;
n= 0 ;
while(n < current->OutEdges())
{DiGrEdge *tmp_edge = current->getOutEdge(n);
DiGrNode *tmp_node = tmp_edge->inNode();
if(tmp_node->getAttribute(``name'') > current->getAttribute(``name''))
{recurse_inorder(tmp_node, blankRule);
}
else{}
n=n +  1 ;
}} while (queue->size() >  0 );

}

int main() {
try{
DiGrNode* binTree[8];
 binTree[0]=new DiGrNode();
 binTree[1]=new DiGrNode();
 binTree[2]=new DiGrNode();
 binTree[3]=new DiGrNode();
 binTree[4]=new DiGrNode();
 binTree[5]=new DiGrNode();
 binTree[6]=new DiGrNode();
 binTree[7]=new DiGrNode();
new DiGrEdge(binTree[4], binTree[2]);
new DiGrEdge(binTree[4], binTree[6]);
new DiGrEdge(binTree[6], binTree[5]);
new DiGrEdge(binTree[6], binTree[7]);
new DiGrEdge(binTree[2], binTree[1]);
new DiGrEdge(binTree[2], binTree[3]);
DiGrNode *tmp_node =  binTree[1];
tmp_node->setAttribute(``name'',  1 );
tmp_node= binTree[2];
tmp_node->setAttribute(``name'',  2 );
tmp_node= binTree[3];
tmp_node->setAttribute(``name'',  3 );
tmp_node= binTree[4];
tmp_node->setAttribute(``name'',  4 );
tmp_node= binTree[5];
tmp_node->setAttribute(``name'',  5 );
tmp_node= binTree[6];
tmp_node->setAttribute(``name'',  6 );
tmp_node= binTree[7];
tmp_node->setAttribute(``name'',  7 );
DiGrNode *start =  binTree[4];
std::cout << ``post-order!'' << std::endl;
recurse_to_children_and_print(start, blankRule);
std::cout << ``in-order!'' << std::endl;
recurse_inorder(start, blankRule);
}
catch(const char *e) {
std::cout << e << std::endl;
}

}
\end{Verbatim}
}

When executed, the output is

{\small
\begin{Verbatim}
post-order!
1
3
2
5
7
6
4
in-order!
1
2
3
4
5
6
7
\end{Verbatim}
}
